10220. Я люблю большие числа!

Для заданного входного n вычислить сумму цифр его факториала.

Вход. Каждая строка содержит целое число n, n £ 1000.

Выход. Вывести сумму цифр числа n!.

Пример входа

5
60
100

Пример выхода

3
288
648

РЕШЕНИЕ

длинная арифметика

Анализ алгоритма

Воспользуемся классом BigInteger. Используя операцию длинного умножения, найдем факториалы всех чисел от 0 до 1000, вычислим сумму их цифр и запомним эти значения в массиве fact. Для каждого входного n будем выводить fact[n].

Реализация алгоритма

Положим длину чисел MAXLENGTH равной 3000. Все значения сумм цифр чисел от 0! до (MAXN-1)! занесем в массив fact. Исходя из условия, положим MAXN=1001.

#define MAXLENGTH 3000

#define MAXN 1001

int fact[MAXN];

Функция DigitSum класса BigInteger возвращает сумму цифр числа.

int DigitSum(void)

{

int i,res = 0;

for(i=0;i<len;i++) res += m[i];

return res;

}

Положим fact[0] = fact[1] = 1, так как 0! = 1! = 1 и сумма цифр этих значений равна 1. В переменной a вычисляем все значения факториалов чисел от 2 до 1000, при помощи функции DigitSum находим их суммы цифр, которые заносим в массив fact.

BigInteger a(1);

fact[0] = fact[1] = 1;

for(i=2;i<MAXN;i++)

{

a = a * i;

fact[i] = a.DigitSum();

}

Для каждого входного i выводим значение fact[i].

while(scanf("%d",&i) == 1)

printf("%d\n",fact[i]);